package com.yulongtian.oneProblemEveryDay.month202211.day20220825;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/find-k-closest-elements/
 *
 * @author YulongTian
 * @date 2022/8/25 - 9:58
 */
public class Test01 {
    public static void main(String[] args) {
        int[] arr = {1,3,3,4,5,7,7,8,8,8};
        System.out.println(findClosestElements(arr, 6, 6));
    }

    public static List<Integer> findClosestElements(int[] arr, int k, int x) {
        int len = arr.length;
        List<Integer> res = new ArrayList<>();
        if (len <= k) {
            for (int i : arr) {
                res.add(i);
            }
            return res;
        }
        if (arr[0] >= x) {
            for (int i = 0; i < k; i++) {
                res.add(arr[i]);
            }
            return res;
        }
        if (arr[len - 1] <= x) {
            for (int i = k; i > 0; i--) {
                res.add(arr[len - i]);
            }
            return res;
        }

        int x_index = 0;

        for (int i = 0; i < len; i++) {
            if (arr[i] == x) {
                x_index = i;
                break;
            }
        }


        List<Integer> dis = new ArrayList<>(k);
        int start = x_index - k + 1 >= 0 ? x_index - k + 1 : 0;


        for (int i = start; i < len - k + 1; i++) {
            if (i == start) {
                for (int j = 0; j < k; j++) {
                    int temp = Math.abs(x - arr[i + j]);
                    dis.add(temp);
                }
                continue;
            }

            if (dis.get(0) > Math.abs(arr[i + k - 1] - x)) {
                dis.remove(0);
                dis.add(Math.abs(arr[i + k - 1] - x));
            }else if(dis.get(0) == Math.abs(arr[i + k - 1] - x)){
                if(arr[i+k-1]==arr[i+k-2]&&arr[i+k-1]<x){
                    dis.remove(0);
                    dis.add(Math.abs(arr[i + k - 1] - x));
                }else{
                    i--;
                    for (int j = 0; j < k; j++) {
                        res.add(arr[i + j]);
                    }
                    return res;
                }

            } else {
                i--;
                for (int j = 0; j < k; j++) {
                    res.add(arr[i + j]);
                }
                return res;
            }

            if (i == len - k) {
                for (int j = 0; j < k; j++) {
                    res.add(arr[i + j]);
                }
                return res;
            }

        }

        return res;
    }


}
